package findtree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树
 */
public class BinarySearchTree {


    //
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode root; //定义头结点

    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * 1.二叉树的插入
     * @param key
     * @return 重复元素 -- 插入失败
     */
    public boolean insert(int key) {
        //1.二叉树的第一个节点
        if(root==null) {
            TreeNode temp = new TreeNode(key);
            root = temp;
            return true;
        }
        //2.寻找插入位置
        TreeNode cur = root;
        TreeNode prev = root;
        while (cur!=null) {
            if(cur.val > key) {  //小于根节点
                prev = cur;
                cur = cur.left;
            }
            else if(cur.val < key) { //大于根节点
                prev = cur;
                cur = cur.right;
            }
            else return false;  //插入重复的元素，返回false，表示插入失败
        }
        //3.插入
        if(prev.val > key) prev.left = new TreeNode(key);
        else prev.right = new TreeNode(key);
        return true;
    }

    /**
     * 2.二叉树的搜索
     * @param key
     * @return 搜索到返回true
     */
    public boolean search(int key) {
        if(root==null) return false;
        TreeNode cur = root;
        while (cur!=null) {
            if(cur.val > key) {  //小于根节点
                cur = cur.left;
            }
            else if(cur.val < key) { //大于根节点
                cur = cur.right;
            }
            else {
                return true;  //插入重复的元素，返回false，表示插入失败
            }
        }
        return false;
    }


    List<Integer> list = new ArrayList<>();

    /**
     * 3.顺序打印二叉搜索树
     * @return
     */
    @Override
    public String toString() {

        inorder(root);

        return list.toString();
    }

    private void inorder(TreeNode cur) {
        //中序遍历二叉搜索树
        if(cur==null) return;
        inorder(cur.left);
        list.add(cur.val);
        inorder(cur.right);
    }

    /**
     * 4.二叉树的删除操作
     * @param key
     * @return
     */
    public boolean remove(int key) {
        if(root==null) return false;

        //1.叶子结点
        //2.左边为空
        //3.右边为空
        //4.两边都不是空

        TreeNode cur = root;
        TreeNode prev = root; // 前驱节点
        while (cur!=null) {
            if(cur.val > key) {  //小于根节点
                prev = cur;
                cur = cur.left;
            }
            else if(cur.val < key) { //大于根节点
                prev = cur;
                cur = cur.right;
            }
            else {
                deleteNode(prev,cur,key);
                return true;
            }
        }
        return false;

    }

    /**
     * 用来执行删除节点操作
     * @param prev
     * @param cur
     * @param key
     */
    private void deleteNode(TreeNode prev,TreeNode cur,int key) {
        //1.叶子结点 -- 直接删除
        if(cur.left==null && cur.right==null) {
            if(prev.left==cur) {
                prev.left=null;
            }else {
                prev.right=null;
            }
        }else if(cur.left!=null && cur.right==null) { //2.非叶子结点，但是右边为null
            if(prev.left==cur) {
                prev.left=cur.left;
            }else {
                prev.right=cur.left;
            }
        }else if(cur.left==null && cur.right!=null) { //3.非叶子结点，但是左边为null
            if(prev.left==cur) {
                prev.left = cur.right;
            }else {
                prev.right = cur.right;
            }
        }else {
            //4.非叶子结点，并且左右都不是空 (难点--使用覆盖删除)
            //删除cur节点，那么去cur的右子树找到最小的结点target，然后把最小的结点覆盖cur，再删除target节点
            //左子树的话就是找到最大的
            TreeNode target = cur.right;
            prev = target;
            while (target.left!=null) {
                prev = target;
                target = target.left; //一直往左边走即是最小值
            }
            cur.val = target.val; // 覆盖操作
            //删除节点
            if(prev.left==target) prev.left = target.right;
            else prev.right = target.right;
        }
    }






}
